Deduplication storage systems, such as EMC Data Domain storage systems, perform deduplication to minimize the amount of storage consumed. Instead of storing two copies of the same piece of data, a single copy is stored (e.g., with two links or identifiers referencing the single copy). In backup and/or archiving applications, significant storage savings can be achieved since backups and archives tend to have copies of identical or substantially similar data. It would be desirable if distributed deduplication storage systems operated in a manner which attempts to optimize deduplication efficiency.